/*
整个解法被作为一个函数给出。该函数返回一个长度为 n 的数组 -- s 的 Z 函数。

数组 z 被初始化为全 0 。当前最右的匹配段被假定为 [0:0] （一个故意为之的不包含任何 i 的小段）。

在循环内，对于 i=1...n-1 ，我们首先确定 z[i] 的初始值 -- 其要么保持为 0 或者使用前述公式计算。

之后，朴素算法尝试尽可能多的增加 z[i] 值。

最后，如果必要（即如果 i+z[i]-1>r ），我们更新最右匹配段 [l:r] 。
*/

vector<int> z_function(string s) {
    int n = (int)s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
 		// i - l 就是 当前位置减去上一个匹配的起始位置 . 
 		// 那么这个z[i-l]也就是最前面的i-l从头开始匹配的位置,所以很巧妙地利用到了前面
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}